package biolabs.util;

import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Undirected graph.
 *
 * <b>The implementation is not thread-safe.</b> If multiple threads make
 * structural modifications to the graph, the access must be synchronized
 * externally.
 *
 * @param <V> vertex data type
 * @param <E> edge data type
 *
 * @author Tomas Mikula
 */
public class Graph<V, E> {
	
	public static class Vertex<V,E> {
		
		private static class OutgoingEdgeFilter<V,E> implements Filter<Edge<V,E>> {

			private final V vertex;

			public OutgoingEdgeFilter(V v){
				this.vertex = v;
			}

			@Override
			public boolean allows(Edge<V, E> e) {
				return e.u == vertex;
			}

		}

		private final V v;
		private final List<Edge<V, E>> edges;

		private Vertex(V v){
			this(v, new LinkedList<Edge<V,E>>());
		}

		private Vertex(V v, List<Edge<V, E>> neighbors){
			this.v = v;
			this.edges = neighbors;
		}
		
		public V getData(){
			return v;
		}
		
		public Collection<Edge<V,E>> incidentEdges() {
			return Collections.unmodifiableCollection(edges);
		}
		
		public boolean hasNeighbor(V w){
			for(Edge<V,E> e: edges)
				if( e.u==w && e.v==v || e.u==v && e.v==w )
					return true;
			return false;
		}
		
		public Collection<V> neighborData(){
			Transformation<Edge<V,E>, V> tr = new Transformation<Edge<V,E>, V>(){
				@Override
				public V apply(Edge<V, E> e) {
					if(e.u == v)
						return e.v;
					else
						return e.u;
				}
			};
			return new TransformingCollection<Edge<V,E>, V>(edges, tr);
		}

		private void addEdge(Edge<V,E> e){
			edges.add(e);
		}
		
		private boolean removeEdgeTo(V w){
			for(Iterator<Edge<V,E>> i=edges.iterator(); i.hasNext(); ){
				Edge<V,E> e = i.next();
				if(e.u == w || e.v == w){
					i.remove();
					return true;
				}
			}
			return false;
		}

		private Iterable<Edge<V,E>> outgoingEdges() {
			return new FilteringIterable<Edge<V,E>>(edges, new OutgoingEdgeFilter<V,E>(v));
		}
	}
	
	public static class Edge<V,E> {
		private final V u, v;
		private final E e;
		
		private Edge(V u, E e, V v){
			this.u = u;
			this.v = v;
			this.e = e;
		}

		public V getU(){
			return u;
		}

		public V getV(){
			return v;
		}

		public V getOppositeEndOf(V w){
			if(w == u)
				return v;
			if(w == v)
				return u;
			throw new IllegalArgumentException("Given vertex is not an endpoint of this edge");
		}

		public E getData(){
			return e;
		}
	}


	private final Map<V, Vertex<V,E>> nodes;

	public Graph(){
		this.nodes = new HashMap<V, Vertex<V,E>>();
	}

	/* ***** MODIFICATION METHODS ***** */

	public boolean addVertex(V v){
		if(nodes.containsKey(v))
			return false;
		nodes.put(v, new Vertex<V,E>(v));
		return true;
	}

	public boolean addEdge(V u, E e, V v){
		// check presence of u and v
		Vertex<V,E>
			uu = nodes.get(u),
			vv = nodes.get(v);
		if( uu == null || vv == null )
			return false;

		// check if u and v are not already connected
		if( uu.hasNeighbor(v) )
			return false;

		// create an edge between u and v
		Edge<V,E> edge = new Edge<V,E>(u, e, v);
		uu.addEdge(edge);
		vv.addEdge(edge);

		return true;
	}

	public boolean removeVertex(V v){
		
		// check presence of v
		Vertex<V, E> vv = nodes.get(v);
		if(vv == null)
			return false;

		// remove v from neighbor lists of its neighbors
		for(V u: vv.neighborData()){
			if(!nodes.get(u).removeEdgeTo(v))
				assert false : "Removing non-existent edge";
		}

		// remove v itself
		nodes.remove(v);

		return true;
	}

	public boolean removeEdge(V u, V v){
		// check that both vertices belong to this graph
		Vertex<V,E>
			uu = nodes.get(u),
			vv = nodes.get(v);
		if( uu == null || vv == null )
			return false;

		// remove from each other's neighbors
		if( !uu.removeEdgeTo(v) )
			return false;
		else
			if( !vv.removeEdgeTo(u) )
				assert false : "Assymetric undirected graph";

		return true;
	}


	/* ***** VIEWS ***** */

	/**
	 * Returns a read-only collection view of graph vertices.
	 * If graph is modified while iterating over the returned collection,
	 * the result of iteration is undefined.
	 */
	public Collection<Vertex<V,E>> vertices(){
		return Collections.unmodifiableCollection(nodes.values());
	}

	/**
	 * Returns a read-only view of data stored in vertices of this graph.
	 * If graph is modified while iterating over the returned collection,
	 * the result of iteration is undefined.
	 */
	public Collection<V> vertexValues(){
		return Collections.unmodifiableCollection(nodes.keySet());
	}

	public Iterable<Edge<V,E>> edges(){
		Transformation<Vertex<V,E>, Iterable<Edge<V,E>>> tr =
			new Transformation<Vertex<V,E>, Iterable<Edge<V,E>>>(){
				@Override
				public Iterable<Edge<V, E>> apply(Vertex<V, E> v) {
					return v.outgoingEdges();
				}
			};
		TransformingCollection<Vertex<V,E>, Iterable<Edge<V,E>>> iterables =
			new TransformingCollection<Vertex<V,E>, Iterable<Edge<V,E>>>(
					nodes.values(), tr );
		return new ConcatenatingIterable<Edge<V,E>>(iterables);
	}
}